#
# @lc app=leetcode.cn id=131 lang=python
#
# [131] 分割回文串
#

# @lc code=start
class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        self.s = s
        self.result = []
        self.subresult = []
        self.loop(0)
        return self.result


    def loop(self, index):
        if index == len(self.s):
            self.result.append(self.subresult[:])
            return 

        for i in range(index, len(self.s)):
            if self.ispalindromic(index, i):
                self.subresult.append(self.s[index: i+1])
                self.loop(i+1)
                self.subresult.pop()
    
    def ispalindromic(self, i, j):
        while i<j:
            if self.s[i] == self.s[j]:
                i += 1
                j -= 1
            else:
                return False
        return True
        
# @lc code=end

